package class4;

/**
 * https://leetcode.cn/problems/hamming-distance/
 * 汉明距离
 * 说明：
 * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
 * 例如：x^y 就能取出x和y数字中不同1的位置所组成的十进制数
 */
public class Code12_hammingDistance {

    public static void main(String[] args) {
        int x = 1, y = 4;
        int i = hammingDistance(x, y);
        System.out.println("i = " + i);
    }

    public static int hammingDistance(int x, int y) {
        return cntOnes(x ^ y);
    }

    public static int cntOnes(int n) {
        /**
         *    1 1 1 1 1 0 0 1    =    0 1 1 1 1 1 0 0 (>>>1)
         *  & 0 1 0 1 0 1 0 1         0 1 0 1 0 1 0 1 (0x55555555)
         * s1:0 1 0 1 0 0 0 1      s2:0 1 0 1 0 1 0 0
         * s2:0 1 0 1 0 1 0 0
         * + :1 0 1 0 0 1 0 1    =     2   2   1   1
         *--------------------------------------------------------------------
         *    1 0 1 0 0 1 0 1    =    0 0 1 0 1 0 0 1 (>>>2)
         *  & 0 0 1 1 0 0 1 1         0 0 1 1 0 0 1 1 (0x33333333)
         * s1:0 0 1 0 0 0 0 1      s2:0 0 1 0 0 0 0 1
         * s2:0 0 1 0 0 0 0 1
         * + :0 1 0 0 0 0 1 0    =    4          2
         * -------------------------------------------------------------------
         *    0 1 0 0 0 0 1 0    =    0 0 0 0 0 1 0 0 (>>>4)
         *  & 0 0 0 0 1 1 1 1         0 0 0 0 1 1 1 1 (0x0f0f0f0f)
         * s1:0 0 0 0 0 0 1 0      s2:0 0 0 0 0 1 0 0
         * s2:0 0 0 0 0 1 0 0
         * + :0 0 0 0 0 1 1 0    =             6
         */
        n = (n & (0x55555555)) + ((n >>> 1) & 0x55555555);
        n = (n & (0x33333333)) + ((n >>> 2) & 0x33333333);
        n = (n & (0x0f0f0f0f)) + ((n >>> 4) & 0x0f0f0f0f);
        n = (n & (0x00ff00ff)) + ((n >>> 8) & 0x00ff00ff);
        n = (n & (0x0000ffff)) + ((n >>> 16) & 0x0000ffff);
        return n;
    }
}
